package 中等.动态规划.子序列;

import java.util.Arrays;

/**
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 
 * 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所
 * 有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
 */
public class 最长数对链_646 {

    public static void main(String[] args) {

        int[][] pairs = new int[][]{{1, 2}, {2, 3}, {3, 4}};
        System.out.println(findLongestChain(pairs));

    }

    /**
     * 问题：
     * 因为可以任意顺序返回，以i元素结尾的数对链中，之前的元素可以从
     * i-x的元素中取到，也可以从i+x的元素中取到，那么动态规划就进行不了
     * 解决：
     * 先对pair[0]进行排序，那么以pairs[i]结尾的数对链，之前的元素只能是
     * <i的元素
     * 例如：
     * (2,3) (1,3) (4,5)->(1,3) (2,3) (4,5)
     * (2,3)之前的元素不能是(4,5)
     * 2<4<5 所以5不能比2小
     * <p>
     * 子问题：
     * 以i结尾的数对列最长长度是多少
     * 状态转移方程
     * 存在某一个元素（a,b）（c,d） b<c
     * if(pairs[pre][1]<pairs[i][0])  dp[i]=Math.max(dp[i],dp[pre]+1)
     * 不存在，最小为1
     *
     * @param pairs
     * @return
     */
    public static int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (o1, o2) -> o1[0] - o2[0]);
        int ans = 1;
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);  //最小长度为1
        for (int cur = 1; cur < pairs.length; cur++) {
            for (int pre = 0; pre < cur; pre++) {
                if (pairs[pre][1] < pairs[cur][0]) {
                    dp[cur] = Math.max(dp[cur], dp[pre] + 1);
                }
            }
            ans = Math.max(ans, dp[cur]);
        }
        return ans;
    }

}
